package cn.hycat.leetcode.middle;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
/*      记忆化搜索 -> 动态规划
        给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
        计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回-1 。
        你可以认为每种硬币的数量是无限的。
        示例1：

        输入：coins = [1, 2, 5], amount = 11
        输出：3
        解释：11 = 5 + 5 + 1
        示例 2：

        输入：coins = [2], amount = 3
        输出：-1
        示例 3：

        输入：coins = [1], amount = 0
        输出：0*/
public class L322零钱兑换 {
    public static void main(String[] args) {
        int[] coins = {1,2,5};
        System.out.println(coinChange(coins, 11));
    }

    public static int coinChange(int[] coins, int amount) {
        int[][] dp = new int[coins.length+1][amount+1];
        return dfs(coins, 0, amount, dp);
    }

    //记忆化搜索 dfs(index, amount)表示 从index开始考虑 此时amount还剩多少
    public static int dfs(int[] coins, int index, int amount, int[][] dp) {
        //钱变为负数或走到最后钱还是正数：失败
        if(amount < 0 || index == coins.length)
            return -1;
        if(dp[index][amount] != 0) {
            return dp[index][amount];
        }
        //钱正好用完：成功
        if(amount == 0)
            return 0;
        //钱>0并且index没走到头：继续搜索
        int p1 = dfs(coins, index+1, amount, dp);
        int p2 = dfs(coins, index+1, amount - coins[index], dp);
        int p3 = dfs(coins, index, amount - coins[index], dp);
        if(p1 == -1 && p2 == -1 && p3 ==-1) {
            dp[index][amount] =  -1;
        } else if(p2 == -1 && p1 == -1) {
            dp[index][amount] =  p3 + 1;
        } else if(p1 == -1 && p3 == -1) {
            dp[index][amount] =  p2 + 1;
        } else if(p2 == -1 && p3 == -1){
            dp[index][amount] =  p1;
        } else if(p1 == -1) {
            dp[index][amount] =  Math.min(p2 + 1, p3 + 1);
        } else if(p2 == -1) {
            dp[index][amount] =  Math.min(p1, p3 + 1);
        } else if(p3 == -1) {
            dp[index][amount] =  Math.min(p1, p2 + 1);
        } else {
            dp[index][amount] =  Math.min(p1, Math.min(p2 + 1, p3 + 1));
        }
        return dp[index][amount];
    }
}
